3348. Cows
Your friend to the south is
interested in building fences and turning plowshares into swords. In order to
help with his overseas adventure, they are forced to save money on buying fence
posts by using trees as fence posts wherever possible. Given the locations of
some trees, you are to help farmers try to create the largest pasture that is
possible. Not all the trees will need to be used.
However, because you will oversee the
construction of the pasture yourself, all the farmers want to know is how many
cows they can put in the pasture. It is well known that a cow needs at least 50
square metres of pasture to survive.
Input. The first
line of input contains a single integer n
(1 ≤ n ≤ 10000),
containing the number of trees that grow on the available land. The next n lines contain the integer coordinates
of each tree given as two integers x
and y separated by one space (where
-1000 ≤ x, y ≤ 1000). The integer coordinates correlate exactly to
distance in metres (e.g., the distance between coordinate (10; 11) and (11; 11)
is one metre).
Output. You are
to output a single integer value, the number of cows that can survive on the
largest field you can construct using the available trees.
|
Sample input |
Sample output |
|
4 0 0 0 101 75 0 75 101 |
151 |
РЕШЕНИЕ
геометрия - выпуклая
оболочка
Анализ алгоритма
Строим
выпуклую оболочку. Далее по формуле Сюрвейера ищем ее площадь. Получим площадь
пастбища area. Поскольку каждой корове следует выделить минимум 50
квадратных метров, то 
коров сможет выжить.
Реализация алгоритма
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#define EPS
1e-6
#define PI
acos(-1.0)
using namespace std;
class Point
{
public:
int x, y;
Point(int x =
0, int y = 0)
{
this->x
= x; this->y = y;
}
double len2()
const {return
x*x + y*y;}
};
Point operator+ (Point a, Point b)
{
return
Point(a.x+b.x,a.y+b.y);
}
Point operator- (Point a, Point b)
{
return
Point(a.x-b.x,a.y-b.y);
}
vector<Point>
v, hull;
int i, n,
cur, a, b;
double area;
Point
Center;
// the angle is in the range [-PI..PI]
double
PolarAngle(Point p)
{
return
atan2(1.0*p.y,1.0*p.x);
}
int
f(Point a, Point b)
{
// if angles are
equal, sort in increasing ditance from (0,0)
if
(fabs(PolarAngle(a) - PolarAngle(b)) < EPS)
return
a.len2() < b.len2();
return
PolarAngle(a) < PolarAngle(b);
}
int
TurnLeft(Point a, Point b, Point c)
{
Point q = b - a, w = c - b;
return q.x *
w.y - w.x * q.y > EPS;
}
int main(void)
{
scanf("%d",&n);
for(i = 0; i
< n; i++)
{
scanf("%d
%d",&a,&b);
v.push_back(Point(a,b));
}
for(i = 1; i
< n; i++)
{
if (v[i].x
< v[0].x) swap(v[i],v[0]);
if ((v[i].x
== v[0].x) && (v[i].y < v[0].y)) swap(v[i],v[0]);
}
Center = v[0];
for(i = 0; i
< n; i++) v[i] = v[i] - Center;
sort(v.begin()+1,v.end(),f); v.push_back(v[0]); n++;
for(cur = 1,
i = 2; i < n; i++)
{
while(
(cur > 0) && !TurnLeft(v[cur-1],v[cur],v[i]))
cur--;
v[++cur] = v[i];
}
for(i = 0; i
<= cur; i++) v[i] = v[i] + Center;
for(area = i
= 0; i < cur; i++)
area +=
v[i+1].y * v[i].x - v[i].y * v[i+1].x;
area /= 2.0;
printf("%.0lf\n",floor(area
/ 50));
return 0;
}
Реализация алгоритма – сортировка точек через
направление поворота
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
class Point
{
public:
int x, y;
Point(int x =
0, int y = 0)
{
this->x
= x; this->y = y;
}
double len2()
const {return
x*x + y*y;}
};
Point operator+ (Point a, Point b)
{
return
Point(a.x+b.x,a.y+b.y);
}
Point operator- (Point a, Point b)
{
return
Point(a.x-b.x,a.y-b.y);
}
vector<Point>
v, hull;
int i, n,
cur, a, b;
double area;
int
f(Point a, Point b)
{
Point q = a - v[0], w = b - a;
if(q.x * w.y
> w.x * q.y)
return 1;
if(q.x * w.y
== w.x * q.y)
return
a.len2() < b.len2();
return 0;
}
int
TurnLeft(Point a, Point b, Point c)
{
Point q = b - a, w = c - b;
return q.x *
w.y > w.x * q.y;
}
int main(void)
{
scanf("%d",&n);
for(i = 0; i
< n; i++)
{
scanf("%d
%d",&a,&b);
v.push_back(Point(a,b));
}
for(i = 1; i
< n; i++)
{
if (v[i].x
< v[0].x) swap(v[i],v[0]);
if ((v[i].x
== v[0].x) && (v[i].y < v[0].y)) swap(v[i],v[0]);
}
sort(v.begin()+1,v.end(),f); v.push_back(v[0]); n++;
for(cur = 1,
i = 2; i < n; i++)
{
while( (cur
> 0) && !TurnLeft(v[cur-1],v[cur],v[i])) cur--;
v[++cur] = v[i];
}
for(area = i
= 0; i < cur; i++)
area +=
v[i+1].y * v[i].x - v[i].y * v[i+1].x;
area /= 2.0;
printf("%.0lf\n",floor(area
/ 50));
return 0;
}